package aco;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * the controller is the central part of the algorithm, which reads the benchmark data,
 * initializes the data structures, builds an initial solution using nearest neighbor heuristic
 * and starts the ant colony, once the working day has started
 */
public class Controller {

    //length of a working day in seconds(工作日的时长)
    // 可以理解为，工作日的时长为100个时间单位
    private static int workingDay = 100;

    //number of time slices（50个时间片段）
    private static int noTimeSlices = 50;

    //file name to be used for input data set(算例文件的名字)
    public static String vrpInstance = "r103";   //r104

    //dynamic level, which gives the proportion of the dynamic requests (available time > 0) from the DVRPTW instance
    private static double dynamicLevel = 0.1;  //0.0  //0.1  //0.5  //1.0

    private static double scalingValue; // 这个参数好像是计算距离矩阵的时候用到过.

    private static int idLastAvailableNode = 0;

    public static int addedNodes = 0; // 增加的结点的数量????

    public static double getScalingValue() {
        return scalingValue;
    }

    public static void setScalingValue(double scalingValue) {
        Controller.scalingValue = scalingValue;
    }

    public static int getIdLastAvailableNode() {
        return idLastAvailableNode;
    }

    public static void setIdLastAvailableNode(int idLastAvailableNode) {
        Controller.idLastAvailableNode = idLastAvailableNode;
    }

    /**
     * get a list of new available (known) nodes at the given time moment
     * 返回新产生的可访问城市的链表,所以不包括以前已知的可访问城市节点
     *
     * @param dynamicRequests:动态请求
     * @param time:当前时间
     * @return:新产生的可访问城市节点的链表（相当于返回新出现的订单的链表）
     */
    public static ArrayList<Integer> countNoAvailableNodes(ArrayList<Request> dynamicRequests, double time) {
        int i, id;
        int pos = Controller.getIdLastAvailableNode();
        ArrayList<Integer> nodesList = new ArrayList<Integer>();

//    	dynamicRequests表示动态请求的集合(集合中的节点按照出现的时间先后顺序进行排列)
        for (i = pos; i < dynamicRequests.size(); i++) {
//            如果当前时间不早于，请求城市节点的可访问时间，则这个请求城市是可访问的
            if (time >= dynamicRequests.get(i).getAvailableTime()) {
                id = dynamicRequests.get(i).getId() - 1;
                nodesList.add(id);
            } else {
                break;
            }
        }
        Controller.setIdLastAvailableNode(i);

        return nodesList;
    }

    /**
     * get the position of the last committed node in the tour designated by indexTour from the best so far ant
     *
     * @param indexTour:路径编号
     * @return 返回指定路径上的, 最后一个被锁定的城市节点在路径中的位置(路径中的位置要从0开始数)
     */
    public static int getLastCommitedPos(int indexTour) {
        int pos = 0;
        int node;
        int tourLength;

        if (indexTour < Ants.best_so_far_ant.usedVehicles) {
            tourLength = Ants.best_so_far_ant.tours.get(indexTour).size();
            for (int i = 1; i < tourLength - 1; i++) {
                node = Ants.best_so_far_ant.tours.get(indexTour).get(i);
                if (Ants.committedNodes[node]) {
                    pos++;
                } else {
                    break;
                }
            }
        }
        return pos;
    }

    /**
     * check if there are any nodes in the tours of the best so far solution that should be marked as committed
     * 检查是否存在需要被锁定的节点(在指定的时间片段内)
     *
     * @param bestAnt:全局最优蚂蚁
     * @param instance:问题实例
     * @param indexTimeSlice:时间片段编号
     * @param lengthTimeSlice:单个时间片段的长度
     * @return
     */
    public static boolean checkNewCommittedNodes(Ants.Ant bestAnt, VRPTW instance, int indexTimeSlice, double lengthTimeSlice) {
        boolean result = false;
        int indexTour = 0;
        int tourLength = 0;
        int node = 0, startPos = 0, count = 0;

        while (indexTour < bestAnt.usedVehicles) {
            if (count >= 50) {
                System.out.println("Index tour=" + indexTour + ", used vehicles=" + bestAnt.usedVehicles + ", tour length=" + tourLength);
            }

            //skip for already committed nodes(跳过已经锁定的城市节点)
            tourLength = bestAnt.tours.get(indexTour).size();
            startPos = getLastCommitedPos(indexTour);
            for (int i = startPos + 1; i < tourLength - 1; i++) {
                node = bestAnt.tours.get(indexTour).get(i);
//    			check condition for a node to be committed
//				检查是否满足锁定条件: 城市的开始服务时间不能晚于时间片段的结束时间
                if (bestAnt.beginService[node + 1] <= indexTimeSlice * lengthTimeSlice) {
                    if (!Ants.committedNodes[node]) {
                        return true;
                    } else {
                        continue;
                    }
                } else {
                    indexTour++;
                    break;
                }
            }
//    		if all the nodes from this tour are committed, move to the next tour
//    		for checking if it contains nodes that must be committed
            if (indexTour < bestAnt.usedVehicles) { // 感觉这个判断没有用处
                startPos = getLastCommitedPos(indexTour);
                tourLength = bestAnt.tours.get(indexTour).size();
//    			如果开始位置是仓库的位置，说明此路径为新路径(空路径),直接跳过此仓库
                if (startPos == tourLength - 2) {
                    indexTour++;
                }
            }
            count++;
        }
        return result;
    }


    /**
     * commit nodes from the tours of the best so far solution,
     * that will have their position fixed when they will be copied in the ants'solutions
     * block part of the best solution that is being/has been visited
     * 把满足指定时间片段约束的城市节点,全部锁定
     *
     * @param bestAnt
     * @param instance
     * @param indexTimeSlice
     * @param lengthTimeSlice
     */
    public static void commitNodes(Ants.Ant bestAnt, VRPTW instance, int indexTimeSlice, double lengthTimeSlice) {
        int indexTour = 0;
        int tourLength = 0;
        int node = 0, startPos = 0, count = 0;

        while (indexTour < bestAnt.usedVehicles) {
            //skip for already committed nodes
            tourLength = bestAnt.tours.get(indexTour).size();
            if (count >= 50) {
                System.out.println("Index tour=" + indexTour + ", used vehicles=" + bestAnt.usedVehicles + ", tour length=" + tourLength);
            }
            startPos = getLastCommitedPos(indexTour);
            for (int i = startPos + 1; i < tourLength - 1; i++) {
                node = bestAnt.tours.get(indexTour).get(i);
                //check condition for a node to be committed
                if ((bestAnt.beginService[node + 1] <= indexTimeSlice * lengthTimeSlice) &&
                        (!Ants.committedNodes[node])) {
                    Ants.committedNodes[node] = true;
                    //Ants.lastCommitted.set(indexTour, i);
                } else {
                    indexTour++;
                    break;
                }
            }
            //if all the nodes from this tour were committed (the depot from the start and
            //end of a tour are assumed to be committed by default), move to the next tour
            if (indexTour < bestAnt.usedVehicles) {
                startPos = getLastCommitedPos(indexTour);
                tourLength = bestAnt.tours.get(indexTour).size();
                if (startPos == tourLength - 2) {
                    indexTour++;
                }
            }
            count++;
        }
    }

    // 主函数,整个项目的入口
    public static void main(String[] args) {
        long startTime, endTime;// 执行ACS优化算法的开始时间和结束时间
        double currentTime, scalingValue, newStartWindow, newEndWindow, newServiceTime, newAvailableTime;
        // counter which stores the number of the current time slice that we are during the execution of the algorithm,
        // which simulates a working day
        int currentTimeSlice = 1; // 时间片段序号（当前为第一个时间片段）
        boolean threadStopped = false; // 是否ACS线程被停止
        boolean isNewNodesAvailable = false; // 是否出现新的可访问节点
        boolean isNewNodesCommitted = false; // 是否有新的节点需要被锁定
        /* keeps the last index/position in the array of dynamic requests sorted ascending by available time
            of the recent request which became available in the last time slice
        将动态请求列表中的最后一个索引按照[在上一个时间片段中可访问的最近请求的]可访问时间进行升序排列,
        意思可能是: 把新出现的可访问请求节点,按照可访问时间升序排列 */
        int countApriori, lastPos;
        ArrayList<Integer> newAvailableIdNodes = new ArrayList<Integer>(); // 新的可访问城市节点编号列表
        ArrayList<Integer> idKnownRequests = new ArrayList<Integer>(); // 已知请求编号列表
        ArrayList<Integer> lastCommitedIndexes; // 储存, 每条路径上的,最后一个锁定城市在此路径中的位置的列表
        double sum;

        // 进行测试的次数，暂定为2
        for (int trial = 0; trial < 2; trial++) {

            // 1. 从txt文件中,把问题的信息读取到vrpInstance问题中
            // reads benchmark data; read the data from the input file
            String dvrptwInstance = vrpInstance + "-" + dynamicLevel;
            String fileName = dvrptwInstance + ".txt";
            DataReader reader = new DataReader(fileName);
            // read the data from the file。将问题的信息读取到vrpInstance中
            VRPTW vrpInstance = reader.read();
            System.out.println("DVRPTW_ACS MinSum >> Solving dynamic VRPTW instance: " + dvrptwInstance);

            // 2. 计算先验请求的数量，计算scalingValue
            // 2.1 计算先验请求的数量,即工作日开始之前就已知的请求城市
            //include in the counting also the depot, which is assumed to be apriori known
            countApriori = vrpInstance.getIdAvailableRequests().size();
            System.out.println("No. of customers' requests (except the depot): " + VRPTW.n + ", among which " + countApriori + " are apriori known (available nodes excluding the depot) and " + vrpInstance.getDynamicRequests().size() + " are dynamic requests");

            // 2.2 计算scalingValue,用于调整所有与时间相关的值。
            // scalingValue是一个时间比例:工作日的时长/仓库提供服务的时长
            // compute the scaling value with which we can scale all time-related values
            Request depotReq = vrpInstance.getRequests().get(0); // 仓库节点
            scalingValue = (double) workingDay / (double) (depotReq.getEndWindow() - depotReq.getStartWindow());
            Controller.setScalingValue(scalingValue);

            // 2.2.1 使用scalingValue初始化优化程序
            // adjust distances between nodes (cities) according to this scale value
            InOut.init_program(args, trial, vrpInstance, scalingValue); // 这里面的args需要找地方输入

            // 2.2.2 使用scalingValue调整时间窗的开始时间和结束时间
            //adjust for each request, all the time related values according to the length of the working day we are simulating
            if (scalingValue != 0) {
                System.out.println("Scalling value = " + scalingValue);
                for (Request req : vrpInstance.getRequests()) {
                    newStartWindow = req.getStartWindow() * scalingValue;
                    req.setStartWindow(newStartWindow);
                    newEndWindow = req.getEndWindow() * scalingValue;
                    req.setEndWindow(newEndWindow);
                    newServiceTime = req.getServiceTime() * scalingValue;
                    req.setServiceTime(newServiceTime);
                    newAvailableTime = req.getAvailableTime() * scalingValue;
                    req.setAvailableTime(newAvailableTime);
                }
            }

            // 3.根据可访问时间的先后，排列动态请求
            //sorting dynamic requests in ascending order by their available time
            //System.out.println("Sorted list of dynamic requests..");
            ArrayList<Request> dynamicRequests = vrpInstance.getDynamicRequests();
            Collections.sort(dynamicRequests); // 根据可访问时间的先后，排列动态请求
            vrpInstance.setDynamicRequests(dynamicRequests);

            // 4.计算每个城市的【邻近城市序列】,按照距离升序排列
            int[][][] result = new int[2][][];
            result = VRPTW.compute_nn_lists(vrpInstance);
            VRPTW.instance.nn_list = result[0]; // 不包括仓库
            VRPTW.instance.nn_list_all = result[1]; // 包括仓库

            // 5.初始化蚁群的信息素矩阵
            Ants.pheromone = new double[VRPTW.n + 1][VRPTW.n + 1];
            //Ants.total = new double[MTsp.n + 1][MTsp.n + 1];
            //VRPTW_ACS.generateInitialWeights();
            VRPTW_ACS.init_try(vrpInstance);

            // 6.初始化一些参数
            currentTimeSlice = 1; // 从第一个时间片段开始
            idLastAvailableNode = 0;
            addedNodes = 0;
            InOut.noEvaluations = 0; // 改进的次数
            InOut.noSolutions = 0; // 解的数量
            double lengthTimeSlice = (double) workingDay / (double) noTimeSlices; // 单个时域为多久

            // 7.start the ant colony system（这里是对工作日开始之初的静态请求，进行操作）
            startTime = System.currentTimeMillis(); // 蚁群系统的开始执行时间点
            VRPTW_ACS worker = new VRPTW_ACS(threadStopped, vrpInstance);
            Thread t = new Thread(worker); // 蚁群优化线程
            t.start();

//            8. 下面判断什么时候跳出蚁群系统,回到规划器中（有新的城市请求变得可访问；有些节点必须要锁定）
//            这是个一直检查的过程，当工作日结束时，跳出循环
            //check periodically if the problem has changed and new nodes (customer requests) became available
            //or there are nodes from the best so far solution that must be marked as committed
            do {
                //compute current time up to this point（当前时间点的时间）
                endTime = System.currentTimeMillis();
                currentTime = (endTime - startTime) / 1000.0; // 应该是以秒来计量的当前时间
    	   /*if (currentTimeSlice >= 30) {
    		   System.out.println("Trial " + (trial + 1) + " Before if: computed current time=" + currentTime + " currentTimeSlice=" + currentTimeSlice + " lengthTimeSlice=" + lengthTimeSlice);	   
    	   }*/

//              8.1 是否开始了新的时间片段？（如果没有进入新的时间片段，才有必要判断以上两项）当前时间处理上一个时间片段的请求
                //did a new time slice started?
                if (currentTime > currentTimeSlice * lengthTimeSlice) {
                    //advance to next time slice（进入到下一个时间片段）
                    System.out.println("Trial " + (trial + 1) + "; Current time (seconds): " + currentTime + "; new time slice started at " + currentTimeSlice * lengthTimeSlice);

//                    1. 检查是否出现了新的可访问城市节点（并返回访问节点的集合数组）
                    //check if there are new nodes that became available in the last time slice
                    newAvailableIdNodes = countNoAvailableNodes(dynamicRequests, currentTime);
                    //mark the fact that new nodes (from the list of dynamic customer requests) are available
                    int countNodes = newAvailableIdNodes.size();
                    if (countNodes > 0) {
                        isNewNodesAvailable = true;
                    } else {
                        isNewNodesAvailable = false;
                    }

//                    2. 检查是有必须被锁定的城市节点
                    //check if there are nodes that must be marked as committed in the tours of the best so far solution
                    isNewNodesCommitted = checkNewCommittedNodes(Ants.best_so_far_ant, vrpInstance, currentTimeSlice, lengthTimeSlice);

//                    3. 如果有新的可访问节点 或 有必须要被锁定的节点，则停止执行蚁群优化系统（停止执行t线程）
                    //check if new nodes are available (known) or there are parts (nodes) that must be committed from the tours of the best so far solution
                    if (isNewNodesAvailable || isNewNodesCommitted) {
                        //System.out.println("Need to stop ant colony..isNewNodesAvailable=" + isNewNodesAvailable + " isNewNodesCommitted=" + isNewNodesCommitted);

//                        3.1 停止蚁群优化线程
                        // stop the execution of the ant colony thread
                        if (t != null) {
                            worker.terminate();
                            // wait for the thread to stop
                            try {
                                t.join();
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                        }
                        threadStopped = true; // 线程停止

//                        3.2 if there are nodes to be committed（锁定必须要被锁定的节点）
                        if (isNewNodesCommitted) {
                            // commit necessary nodes after the ant colony execution is stopped
                            commitNodes(Ants.best_so_far_ant, vrpInstance, currentTimeSlice, lengthTimeSlice);
                        }
                    }

//                    4. 如果有新的可访问节点，则更新可访问结点的列表（更新请求集合），处理掉新的可访问节点
                    //if there are new available nodes, update the list of available/known nodes (customer requests)
                    if (isNewNodesAvailable) {
                        System.out.print(countNodes + " new nodes became available (known): ");

//                        4.1 更新vrpInstance问题实例的可访问城市列表集合
                        idKnownRequests = vrpInstance.getIdAvailableRequests();
                        for (int id : newAvailableIdNodes) {
                            idKnownRequests.add(id);
                            System.out.print((id + 1) + " ");
                        }
                        vrpInstance.setIdAvailableRequests(idKnownRequests);
                        System.out.println();
                        System.out.println("Number of total available (known) nodes (excluding the depot): " + idKnownRequests.size());

//                        4.2 获取未访问城市的列表集合
                        //insert new available nodes in the best so far solution
                        Ants.best_so_far_ant.toVisit = countNodes;
                        //determine nodes that are not visited yet in the current ant's solution（得到，可访问但是未被访问的城市节点的集合）
                        ArrayList<Integer> unroutedList = Ants.unroutedCustomers(Ants.best_so_far_ant, vrpInstance);

//                        4.3 执行插入启发式，将所有可插入的城市，插入到已有的路径中
                        //skip over committed (defined) nodes when performing insertion heuristic（当前最优解中的，每条路径上的最后一个锁定的城市）
                        lastCommitedIndexes = new ArrayList<Integer>();
                        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
                            lastPos = getLastCommitedPos(index);
                            lastCommitedIndexes.add(lastPos);
                        }
                        InsertionHeuristic.insertUnroutedCustomers(Ants.best_so_far_ant, vrpInstance, unroutedList, 0, lastCommitedIndexes);
                        //System.out.println("After first applying insertion heuristic: Cities to be visited in the best so far solution: " + Ants.best_so_far_ant.toVisit);

//                        4.4 如果还有未访问的可访问城市，则创建新的车辆路径，处理未访问城市
                        //if there are still remaining unvisited cities from the ones that are available
                        //insert an empty tour and add cities in it following nearest-neighbour heuristic
                        int indexTour;
                        while (Ants.best_so_far_ant.toVisit > 0) {

//                            4.4.1 创建新的路径
                            Ants.best_so_far_ant.usedVehicles++;
                            indexTour = Ants.best_so_far_ant.usedVehicles - 1;
                            Ants.best_so_far_ant.tours.add(indexTour, new ArrayList<Integer>());
                            Ants.best_so_far_ant.tours.get(indexTour).add(-1);
                            Ants.best_so_far_ant.tour_lengths.add(indexTour, 0.0);
                            Ants.best_so_far_ant.currentQuantity.add(indexTour, 0.0);
                            Ants.best_so_far_ant.currentTime.add(indexTour, 0.0);
                            //Ants.lastCommitted.add(indexTour, 0);

//                            4.4.2 尽量使用这条新的路径，访问尽可能多的未访问城市
                            //try to add as many unvisited cities/nodes as possible in this newly created tour following the nearest neighbour heuristic
                            Ants.choose_closest_nn(Ants.best_so_far_ant, indexTour, vrpInstance);

//                            4.4.3 因为有了新的路径，所以再执行一次插入启发式
                            //try to insert remaining cities using insertion heuristic
                            if (Ants.best_so_far_ant.toVisit > 0) {
                                //determine nodes that are not visited yet in the current ant's solution
                                unroutedList = Ants.unroutedCustomers(Ants.best_so_far_ant, vrpInstance);
                                //skip over committed (defined) nodes when performing insertion heuristic
                                lastCommitedIndexes = new ArrayList<Integer>();
                                for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
                                    lastPos = getLastCommitedPos(index);
                                    lastCommitedIndexes.add(lastPos);
                                }
                                InsertionHeuristic.insertUnroutedCustomers(Ants.best_so_far_ant, vrpInstance, unroutedList, indexTour, lastCommitedIndexes);
                                //System.out.println("After applying insertion heuristic to the NN tour: Cities to be visited in the best so far solution: " + Ants.best_so_far_ant.toVisit);
                            }

//                            4.4.4 路径最终回到城市
                            //add the depot again to end this tour
                            Ants.best_so_far_ant.tours.get(indexTour).add(-1);
                        }

//                        4.5 更新总的路径长度（在处理完未访问城市节点后，更新总路径长度）
                        sum = 0.0;
                        for (int i = 0; i < Ants.best_so_far_ant.usedVehicles; i++) {
                            Ants.best_so_far_ant.tour_lengths.set(i, VRPTW.compute_tour_length_(Ants.best_so_far_ant.tours.get(i)));
                            sum += Ants.best_so_far_ant.tour_lengths.get(i);
                        }
                        Ants.best_so_far_ant.total_tour_length = sum;

//                        4.6 更新scalingValue（不清楚这个变量有什么实际用处）
                        scalingValue = Controller.getScalingValue();
                        double scalledValue = 0.0;
                        if (scalingValue != 0) {
                            scalledValue = Ants.best_so_far_ant.total_tour_length / scalingValue;
                        }
                        System.out.println("Best ant after inserting the new available nodes>> No. of used vehicles=" + Ants.best_so_far_ant.usedVehicles + " total tours length=" + Ants.best_so_far_ant.total_tour_length + " (scalled value = " + scalledValue + ")");
                    }

//                  5. 进入下一个时间片段
                    currentTimeSlice++;
                }

//                8.2 重启蚁群优化系统
                //restart the colony thread
                if (threadStopped) {
                    //restart the ant colony thread
                    worker = new VRPTW_ACS(threadStopped, vrpInstance);
                    t = new Thread(worker);
                    t.start();
                    threadStopped = false;
                }

//                8.3 如果时间超出工作日，则跳出优化
                if (currentTime >= workingDay) {
                    break;
                }

            } while (true);

//            9. 工作日结束，停止蚁群优化线程
            //working day is over
            //System.out.println("End of working day.." + currentTime);
            //stop the worker thread
            if (t != null) {
                worker.terminate();
                //wait for the thread to stop
                try {
                    t.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

//            10. 下面是一系列的输出操作，输出整个工作日的最终解

//              10.1 计算scalledValue?????????????????????
                scalingValue = Controller.getScalingValue();
                double scalledValue = 0.0;
                if (scalingValue != 0) {
                    scalledValue = Ants.best_so_far_ant.total_tour_length / scalingValue;
                }
                System.out.println("Final best solution >> No. of used vehicles=" + Ants.best_so_far_ant.usedVehicles + " total tours length=" + Ants.best_so_far_ant.total_tour_length + " (scalled value = " + scalledValue + ")");

//              10.2 打印工作日最终解的，每条路径的城市序列
                for (int i = 0; i < Ants.best_so_far_ant.usedVehicles; i++) {
                    int tourLength = Ants.best_so_far_ant.tours.get(i).size();
                    for (int j = 0; j < tourLength; j++) {
                        int city = Ants.best_so_far_ant.tours.get(i).get(j);
                        city = city + 1;  //so as to correspond to the city indexes from the VRPTW input file
                        System.out.print(city + " ");
                    }
                    System.out.println();
                }

//              10.3 打印几句话
                System.out.println("Total number of evaluations: " + InOut.noEvaluations);
                System.out.println("Total number of feasible solutions: " + InOut.noSolutions);
                //System.out.println("Working day is over..");
                boolean isValid = Utilities.checkFeasibility(Ants.best_so_far_ant, vrpInstance, true);
                if (isValid) {
                    System.out.println("The final solution is valid (feasible)..");
                } else {
                    System.out.println("The final solution is not valid (feasible)..");
                }

//              10.4 将最终解的信息，存储到文件中
                //save final solution in a .txt file on the disk
                Utilities.writeFinalSolution(trial, fileName, scalledValue, isValid);
                //save number of used vehicles and total traveled distance in Excel file
                Utilities.writeExcelFinalSolution(trial, scalledValue);
            }
        }
    }

}